package io.github.hadyang.leetcode.offer;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;

import io.github.hadyang.leetcode.TreeNode;

/** @author haoyang.shi */
public class FindPath {

  public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();

    FindPath(res, new LinkedList<>(), root, 0, target);

    res.sort(Comparator.comparingInt(list -> -list.size()));

    return res;
  }

  private void FindPath(
      ArrayList<ArrayList<Integer>> res,
      LinkedList<Integer> path,
      TreeNode node,
      int pathSum,
      int target) {
    if (node == null) {
      return;
    }

    if (pathSum > target) {
      return;
    }

    if (pathSum + node.val == target && node.right == null && node.left == null) {
      ArrayList<Integer> resPath = new ArrayList<>(path);
      resPath.add(node.val);
      res.add(resPath);
      return;
    }

    path.addLast(node.val);

    if (node.left != null) {
      FindPath(res, path, node.left, pathSum + node.val, target);
    }

    if (node.right != null) {
      FindPath(res, path, node.right, pathSum + node.val, target);
    }

    path.removeLast();
  }
}
